|
In graph theory, the thickness of a graph is the minimum number of planar graphs into which the edges of can be partitioned. That is, if there exists a collection of planar graphs, all having the same set of vertices, such that the union of these planar graphs is , then the thickness of is at most .〔.〕〔.〕 In other words, the thickness of a graph is the minimal number of planar subgraphs whose union equals to graph .〔Christian A. Duncan, (On Graph Thickness, Geometric Thickness, and Separator Theorems ), CCCG 2009, Vancouver, BC, August 17–19, 2009〕 Thus, a planar graph has thickness 1. Graphs of thickness 2 are called biplanar graphs. The concept of thickness originates in the 1962 conjecture of Frank Harary: For any graph on 9 points, either itself or its complementary graph is non-planar. The problem is equivalent to determining whether the complete graph is biplanar (it is not, and the conjecture is true). A comprehensive〔 survey on the state of the arts of the topic as of 1998 was written by Petra Mutzel, Thomas Odenthal and Mark Scharbrodt.〔Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, (The Thickness of Graphs: A Survey )〕 ==Specific graphs== The thickness of the complete graph on vertices, , is : except when for which the thickness is three.〔, Theorem 3.2.〕〔.〕 With some exceptions, the thickness of a complete bipartite graph is generally: :〔, Theorem 3.4.〕〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Thickness (graph theory)」の詳細全文を読む スポンサード リンク
|